题目

题目描述

大家都知道Fibonacci数列把，$f_1=1,f_2=1,f_3=2,f_4=3,f_n=f_{n-1}+f_{n-2}$
现在问题很简单，输入$n$和$m$，求$f_n mod m$

输入格式

输入$n,m$

输出格式

输出$f_n mod m$

样例输入

5 1000

样例输出

数据范围与提示

对于$100\%$的数据，$1\le n \le 2\times 10^9,1\le m\le 10^9 + 10$

题解

看到这个数据范围，就知道这肯定不能够一般地递推了。
于是我们要介绍一个工具来帮助我们计算这个数列——矩阵乘法
两个矩阵的乘法仅当第一个矩阵A的列数和第二个矩阵B的行数相等的时候才能定义
就举个例子好了

$\begin{bmatrix}1&0&2\ -1&3&1\end{bmatrix} \times \begin{bmatrix} 3&1 \ 2&1\ 1&0\end{bmatrix}=\begin{bmatrix}(1\times3+0\times2+2\times0)&(1\times1+0\times1+2\times0) \ (-1\times3+3\times2+1\times1)&(-1\times1+3\times1+1\times0)\end{bmatrix}$

那么我们根据这个性质，可以定义两个矩阵，一个是数值矩阵用来存贮递推时的数据，需要有一个初始值，还有一个是递推矩阵用来定义如何递推。
在这道里，我们可以初始化数值矩阵为：

$\begin{bmatrix}f_2&0\f_1&0\end{bmatrix}$

而我们定义递推矩阵为：

$\begin{bmatrix}1&1\1&0\end{bmatrix}$

每次用数值矩阵乘递推矩阵，得到的新矩阵中，数列的下标正好是原来的下标+1，递推得以进行。（请读者自己动手体会一下，不然你永远只为停留在“哇，这个算法好神奇”这个层面）
而对于乘法的递推，我们很容易就想到快速幂，于是这道题就完美解决。
至于如何定义数值矩阵和递推矩阵，我认为还是要多自己思考，多做几次就会了。

代码

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,mod;
long long res[3][3],mul[3][3];
 
void mul_res(){
    long long tmp[3][3];
    memset(tmp,0,sizeof(tmp));
    for(int i=1;i<=2;i++){
        for(int j=1;j<=2;j++){
            for(int k=1;k<=2;k++){
                tmp[i][j]=(tmp[i][j]+mul[i][k]*res[k][j])%mod;
            }
        }
    }
    memcpy(res,tmp,sizeof(tmp));
}
 
void mul_mul(){
    long long tmp[3][3];
    memset(tmp,0,sizeof(tmp));
    for(int i=1;i<=2;i++){
        for(int j=1;j<=2;j++){
            for(int k=1;k<=2;k++){
                tmp[i][j]=(tmp[i][j]+mul[i][k]*mul[k][j])%mod;
            }
        }
    }
    memcpy(mul,tmp,sizeof(tmp));
}
 
int main(){
    cin>>n>>mod;
    if(n<=2){cout<<1;return 0;}
    res[1][1]=res[2][1]=1;
    mul[1][1]=mul[2][1]=mul[1][2]=1;
    n-=2;//初始状态我们可以认为已经是f2的时候了
    while(n){
        if(n&1)mul_res();
        mul_mul();
        n>>=1;
    }
    cout<<res[1][1];
    return 0;
}